home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / route.arc / WORK.C < prev   
Encoding:
C/C++ Source or Header  |  1989-11-24  |  3.1 KB  |  143 lines
  1. #include <stdio.h>
  2.  
  3. #ifndef M_XENIX
  4. #include <stdlib.h>
  5. #endif
  6.  
  7. #include <malloc.h>
  8. #include "cell.h"
  9.  
  10. struct work { /* a unit of work is a hole-pair to connect */
  11.     int FromRow;        /* source row        */
  12.     int FromCol;        /* source column    */
  13.     char far *FromName;    /* source name        */
  14.     int ToRow;        /* target row        */
  15.     int ToCol;        /* target column    */
  16.     char far *ToName;    /* target name        */
  17.     int ApxDist;        /* approximate distance    */
  18.     int Priority;        /* 0=no, 1=yes        */
  19.     struct work far *Next;
  20.     };
  21.  
  22. /* pointers to the first and last item of work to do */
  23. static struct work far *Head = NULL;
  24. static struct work far *Tail = NULL;
  25.  
  26. extern int Ntotal;
  27.  
  28. extern int GetApxDist( int, int, int, int );
  29. extern void Nomem( void );
  30.  
  31. void InitWork( void );
  32. void SetWork( int, int, char far *, int, int, char far *, int );
  33. void GetWork( int *, int *, char far * far *, int *, int *, char far * far * );
  34. void SortWork( void );
  35.  
  36. void InitWork () { /* initialize the work list */
  37.     struct work far *p;
  38.  
  39.     while (p = Head) {
  40.         Head = p->Next;
  41.         _ffree( p );
  42.         }
  43.     Tail = NULL;
  44.     }
  45.  
  46. void SetWork ( r1, c1, n1, r2, c2, n2, pri )
  47.     /* add a unit of work to the work list */
  48.     int r1, c1, r2, c2, pri;
  49.     char far *n1;
  50.     char far *n2;
  51.     {
  52.     struct work far *p;
  53.  
  54.     if (p = (struct work far *)_fmalloc( sizeof(struct work) )) {
  55.         p->FromRow = r1;
  56.         p->FromCol = c1;
  57.         p->FromName = n1;
  58.         p->ToRow = r2;
  59.         p->ToCol = c2;
  60.         p->ToName = n2;
  61.         p->ApxDist = GetApxDist( r1, c1, r2, c2 );
  62.         p->Priority = pri;
  63.         p->Next = NULL;
  64.         if (Head) /* attach at end */
  65.             Tail->Next = p;
  66.         else /* first in list */
  67.             Head = p;
  68.         Tail = p;
  69.         Ntotal++;
  70.         }
  71.     else /* can't get any more memory */
  72.         Nomem();
  73.     }
  74.  
  75. void GetWork ( r1, c1, n1, r2, c2, n2 )
  76.     /* fetch a unit of work from the work list */
  77.     int *r1, *c1, *r2, *c2;
  78.     char far * far *n1;
  79.     char far * far *n2;
  80.     {
  81.     struct work far *p;
  82.  
  83.     if (p = Head) {
  84.         *r1 = p->FromRow;
  85.         *c1 = p->FromCol;
  86.         *n1 = p->FromName;
  87.         *r2 = p->ToRow;
  88.         *c2 = p->ToCol;
  89.         *n2 = p->ToName;
  90.         if (!(Head = p->Next))
  91.             Tail = NULL;
  92.         _ffree( p );
  93.         }
  94.     else { /* none left */
  95.         *r1 = *c1 = *r2 = *c2 = ILLEGAL;
  96.         *n1 = *n2 = NULL;
  97.         }
  98.     }
  99.  
  100. void SortWork () { /* order the work items; shortest first */
  101.     struct work far *p;
  102.     struct work far *q0; /* put PRIORITY CONNECTs in q0 */
  103.     struct work far *q1; /* sort other CONNECTs in q1 */
  104.     struct work far *r;
  105.  
  106.     q0 = q1 = NULL;
  107.     while (p = Head) { /* prioritize each work item */
  108.         Head = Head->Next;
  109.         if (p->Priority) {
  110.             if (!(r = q0)) {
  111.                 p->Next = q0;
  112.                 q0 = p;
  113.                 }
  114.             else {
  115.                 while (r->Next)
  116.                     r = r->Next;
  117.                 p->Next = r->Next;
  118.                 r->Next = p;
  119.                 }
  120.             }
  121.         else if (!(r = q1) || p->ApxDist < q1->ApxDist) {
  122.             p->Next = q1;
  123.             q1 = p;
  124.             }
  125.         else { /* find proper position in list */
  126.             while (r->Next && p->ApxDist >= r->ApxDist)
  127.                 r = r->Next;
  128.             p->Next = r->Next;
  129.             r->Next = p;
  130.             }
  131.         }
  132.     if (p = q0) {
  133.         while (q0->Next)
  134.             q0 = q0->Next;
  135.         q0->Next = q1;
  136.         }
  137.     else
  138.         p = q1;
  139.     /* reposition Head and Tail */
  140.     for (Tail = Head = p; Tail && Tail->Next; Tail = Tail->Next)
  141.         ;
  142.     }
  143.